package pers.qianyu.month_202101.date_20210121;

import org.junit.*;

/**
 * 32. 最长有效括号
 * https://leetcode-cn.com/problems/longest-valid-parentheses/
 * 括号匹配性质
 * 1. 每一个括号的匹配括号是唯一的
 * 2. 将每个左括号看成1， 有括号看成-1的话， 括号的前缀和 >= 0，并且总和为 0
 *
 * @author mizzle rain
 * @date 2021-01-21 14:59
 */
public class LongestValidParentheses {
    private int work(String s) {
        int len = s.length();
        int res = 0;
        for (int start = 0, i = 0, count = 0; i < len; i++) {
            if (s.charAt(i) == '(') {
                count++;
            } else {
                count--;
                if (count < 0) {
                    start = i + 1;
                    count = 0;
                } else if (count == 0) {
                    res = Math.max(res, i - start + 1);
                }
            }
        }
        return res;
    }

    public int longestValidParentheses(String s) {
        if (s.length() == 0) return 0;
        int res = work(s);
        char[] arr = s.toCharArray();
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            arr[i] = (char) (arr[i] ^ 1);
        }
        int left = 0, right = len - 1;
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
        res = Math.max(res, work(new String(arr)));
        return res;
    }

    @Test
    public void test1() {
        int result = new LongestValidParentheses().longestValidParentheses("(()");
        Assert.assertEquals(result, 2);
    }
}
